package com.leetcode;

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 * 解法：用一个int二维数组MaxSide表示 将对应元素作为正方形的右下角时，其最大正方形的边长
 * 1.遇到字符为 '0' ，对应MaxSide填入0
 * 2.当元素为边缘元素时（i = 0 或 j = 0），将其字符对应的数字填入MaxSide中
 * 3.i>0 && j>0时，如果字符为'1'，判断左上角MaxSide[i - 1][j - 1]是否大于0
 *      不大于0：说明与左上角不能构成正方形，该位置(i,j)最大为 1 ，填入MaxSide
 *      大于0：说明与左上角构成正方形，将左上角的最大正方形边长记为 t = MaxSide[i - 1][j - 1]
 *             则左上角的正方形要与该位置(i,j)构成正方形，需要判断
 *            该位置(i,j) 往左数 t个和往上数 t个，是否大于0，
 *            将往左数 和 往上数同时大于 0的个数记为 n，则 n的取值为 n <=t,
 *            所以该位置作为右下角的最大正方形边长MaxSide[i][j] 应填入 n+1
 *  MaxSide中最大的则为二维矩阵的最大正方形的边长
 */
public class MaximalSquare {
    public static void main(String[] args) {
        char[][] matrix = new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'}
                ,{'1','1','1','1','1'},{'1','0','0','1','0'}};
        int area = new Solution().maximalSquare(matrix);
        System.out.println(area);
    }
}
